#ifdef a
#include<stdio.h>
#include"Stack.h"

//快排-》循环实现
void Swap(int* left, int* right) {
	int temp = *left;
	*left = *right;
	*right = temp;
	return;
}

int GetMiddleIndex(int* arr, int left, int right) {
	int mid = left + ((right - left) >> 1);
	if (arr[left] > arr[right - 1]) {
		if (arr[mid] < arr[right - 1])
			return right - 1;
		else if (arr[mid] > arr[left])
			return left;
		else
			return mid;
	}
	else {
		if (arr[left] > arr[mid])
			return left;
		else if (arr[mid] > arr[right - 1])
			return right - 1;
		else
			return mid;
	}
}

void InsertSort(int* arr, int size) {
	for (int i = 1; i < size; i++) {
		int end = i - 1;
		int key = arr[i];
		while (end >= 0 && arr[end] > key) {
			arr[end + 1] = arr[end];
			end--;
		}
		if (arr[end + 1] != key)
			arr[end + 1] = key;
	}
	return;
}
int Partion(int* arr, int left, int right) {
	int cur = left;
	int prev = cur - 1;
	int mid = GetMiddleIndex(arr, left, right);
	if (mid != right - 1)
		Swap(&arr[right - 1], &arr[mid]);
	int key = arr[right - 1];
	while (cur < right - 1) {
		if (arr[cur] < key && ++prev != cur) {
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	if (++prev != right - 1)
		Swap(&arr[prev], &arr[right - 1]);
	return prev;
}

void SortPrint(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

void QuestSortNor(int arr[], int size) {
	Stack s;
	StackInit(&s, size);
	int left = 0;
	int right = size;
	StackPush(&s, right);
	StackPush(&s, left);
	while (!StackIsEmpty(&s)) {
		left = StackTop(&s);
		StackOut(&s);
		right = StackTop(&s);
		StackOut(&s);
	//	if (right - left <= 1)
	//		;//当分散到right - left <= 1时，不需要再次分散了，即该组数据不需要处理
		if (right - left <= 5)
			InsertSort(arr + left, right - left);
		else {
			int div = Partion(arr, left, right);
			//基准值左侧 [left, div)
			//基准值右侧 [div + 1, right)
			StackPush(&s, right);
			StackPush(&s, div + 1);
			StackPush(&s, div);
			StackPush(&s, left);
		}
	}
}

int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	QuestSortNor(arr, size);//[left,right)，下标，左闭右开
	//InsertSort(arr, size);
	SortPrint(arr, size);
	return 0;
}
//#endif 
